The present invention relates generally to communication networks. In particular, the present invention is directed to a method and apparatus for computing, storing and allocating efficient routing connections between nodes in a network.
The performance and efficiency of packet switched networks is heavily dependent upon the routing algorithm implemented at the switches or routers in the network. In particular, the success of distributed audio and video applications hinges on predictable performance in the underlying communication network. A network can provide throughput and delay guarantees by reserving resources for individual connections or flows. The routing algorithm plays a pivotal role in this process by locating paths that can satisfy the performance requirements of arriving connections. This is particularly important for handling high-bandwidth multimedia streams, which often consume a relatively large fraction of the link capacity. Quality-of-service (xe2x80x9cQoSxe2x80x9d) routing has the potential to optimize the usage of network resources and increase the likelihood of accepting new connections by selecting paths based on existing network load and connection traffic parameters. For example, there has been considerable effort and attention to the use of the Internet for the delivery of multimedia traffic. However, because multimedia traffic requires high bandwidth and low latency, the necessity for efficient methods to insure QoS are exacting.
Efficient QoS routing requires effective techniques for computing routes and exchanging link-state information. Link-state is typically propagated in a periodic fashion or in response to a significant change in available capacity. For example, a link may advertise its available bandwidth metric whenever it changes by more than 10% since the previous update message. In addition, a minimum time between update messages is often imposed to avoid excessive link-state update traffic.
QoS guarantees may be implemented by utilizing a connection-oriented environment as opposed to a pure packet switched network. In a connection-oriented environment, a route is determined for each connection or flow and resources are reserved across the route (for each link) for the duration of a connection. In contrast, in a purely packet switched network, the route traversed by individual packets may change during the duration of a connection and resources are not reserved. For example, the ATM Forum""s PNNI (xe2x80x9cPrivate Network Network Interfacexe2x80x9d) standard defines a routing protocol for distributing topology and load information throughout the network, and a signaling protocol for processing the forwarding connection-establishment requests from the source. Similarly, proposed QoS extensions to the OSPF (xe2x80x9cOpen Shortest Path First Routingxe2x80x9d) protocol include an xe2x80x9cexplicit routingxe2x80x9d mechanism for source-directed IP (xe2x80x9cInternet Protocolxe2x80x9d) routing. MPLS (xe2x80x9cMultiProtocol Label Switchingxe2x80x9d) includes a similar technique for constraint-based routing.
A number of packet routing algorithms are known. Many networks such as the Internet employ a static routing scheme. In static routing, all links in a network or domain are associated with a cost metric set in advance by a network adrninistrator. This link metric information is shared across the network domain such that each router is aware of the cost metric for every link in the network. Each router computes the lowest cost route to every other router in the network using a shortest-path algorithm such as Dijkstra""s algorithm. Typically, the set of lowest-cost routes is stored in a routing table or cache at each router. When a packet arrives at a router, the router determines a next router to forward the packet to based upon the information in the static routing tables. Because in static routing all routers utilize identical information, all routers will calculate the same route for a packet. In the case of static link costs, propagation of link-state information between routers in a domain need only be effected infrequently, for example in the case of a link failure. Otherwise, the link state information, by definition, remains current.
However, static routing is inefficient because the load upon each link in a network or domain exhibits dynamic loading. Thus, the static costs associated with each link are inaccurate and the computation of the shortest cost route between a source and destination node, which rely upon these static cost metrics links, will not generate accurate results either. The inefficiency of static routing is most pronounced in a scenario where a highly sought resource suddenly becomes available on a network.
An attractive alternative to static routing is dynamic load-sensitive routing in which the cost metric for each link is continuously updated based upon the load measurement for the link. However, load-sensitive routing has an associated set of significant overheads. Namely, the distribution of link information itself increases the load on the network because each router is required to communicate the cost of each link to other routers as the link-state fluctuates. Second, link-state information may be dated or stale before it is used. This typically occurs because the time required to transmit link-state information is on the same order as the time required to send a packet (because both routing decisions and link-state is transmitted at the packet level). However, although load sensitive routing may prove inefficient at the packet level, in a connection oriented network, where connections are established for some length of time, load sensitive routing can improve efficiency.
A second issue regarding the implementation of routing policies concerns the distribution of the processing load required to compute routes through a network. In hop-by-hop routing, the routing work is shared among all nodes in a route, such that each node computes the next node in the route. However, in general, hop-by-hop routing is inefficient because it is desirable to know in advance, before a route is selected, that each link in the route can support the bandwidth required for a connection. Also, computing load-sensitive routes in a hop-by-hop fashion can lead to routing loops.
In source-directed routing, a source router or switch selects an entire route based upon connection throughput requirements and the available resources in the network (i.e., recent link state information). Each switch maintains its own view of the available link resources, distributes link-state information to other switches, and selects routes for new connections. To improve the scalability of these protocols in large configurations, the switches and links may be assigned to smaller peer groups or areas that exchange detailed link-state information. A network may be comprised of a multitude of peer groups or areas. Within a domain, each router has global knowledge of all links in its peer groups or areas and the associated cost metrics for these links. However, routers in a peer group or area typically only have limited knowledge about the link-state of the routers and links in external peer groups.
A goal of source-directed link-state routing is to minimize the probability that a chosen connection route will fail due to inadequate bandwidth. When a new connection is requested (i.e., the source is alerted to the bandwidth and destination for a connection), the source computes a route for the connection using the most recent link-state information. Based on the required bandwidth for the connection, the source node may eliminate some links because they cannot support the required bandwidth. For example, infeasible links may be pruned using the test (util(1)+b greater than 1?), where util(1) is a utilization parameter associated with the current connection request and b is the bandwidth currently used on the link. Then, the source router runs a shortest path algorithm (e.g., Dijkstra""s algorithm) in order to calculate the lowest cost path to the destination node. These costs are typically based on the load at each link. The shortest path is usually computed by analyzing the load on each link and hop count. It is undesirable to choose routes that require an excessive number of hops, even though the route may be minimally loaded. A routing failure occurs when the source cannot find a feasible path to the destination.
If a route is found by the source, the route is tested to insure that there is sufficient bandwidth along each link to accommodate the connection. Typically, the source attempts to establish a virtual circuit on the chosen route by sending a set-up message that travels hop-to-hop (hop-by-hop signaling) through the network on the selected route to the destination node. Each switch or router along the way passes the test connection to the next router or switch until the set-up message reaches the destination, at which time the connection is established if possible. If one or more links cannot support the bandwidth demanded for the traffic (i.e., a set-up failure occurs) the connection is not established and the source may decide to try a new route that excludes the offending link or may simply block the connection. This may happen, for example, if the link information is out of date and the link no longer has the available bandwidth to support the connection. If the connection is accepted, the source router initiates hop-by-hop signaling to cause each router along the route to reserve the requisite bandwidth for the connection.
Efficient source-directed link-state routing imposes counterbalancing demands. First, the link-state information must be as current as possible to prevent the situation in which a selected link cannot actually support the traffic. However, distributing link load information, signaling and computing routes for new connections can consume considerable bandwidth, memory and processing resources. In addition, the route computations and signaling attempts consume processing resources at the switches and introduce set-up latency for each accepted connection. Minimizing these overheads is particularly important during periods of transient overload such as bursty connection arrivals or rerouting of traffic after a link failure.
In addition, the computational bandwidth must be minimized. Distributing link load information and computing routes for new connections can consume considerable bandwidth, memory and processing resources. Controlling these overheads in large backbone networks requires a careful trade-off between accuracy and complexity.
Most previous research on QoS routing has investigated on-demand policies that compute a path at connection arrival. Recent work has considered precomputation or path-caching schemes that attempt to amortize the overheads of route computation by reusing the paths for multiple connection requests. Precomputing routes offers a number of benefits including the amortization of computation overhead over multiple flows, simplification of CPU provisioning with periodic recomputation and reduced set-up delay by avoiding on-demand computation.
However, path precomputation introduces a trade-off between processing overheads and the quality of the routing decisions. Previous work on precomputed routes has focused on quantifying this trade-off and developing guidelines for when to recompute routes, focusing on path caching policies, performance evaluation and algorithmic issues. In particular, known methods for precomputation of network routes involve storing routes in a separate data structure and considering different policies for updating and replacing precomputed routes. For example, M. Peyravian and A. D. Kshemkalyan, xe2x80x9cNetwork path caching: Issues, algorithms and a simulation study,xe2x80x9d Computer Communications, vol. 20, pp. 605-614, 1997 describes a policy that invalidates cache entries based on the number of link-state updates that have arrived for links in the precomputed paths. The proposed algorithms in this reference also check the current link-state when selecting a path from the cache and allow recomputation when the cached paths are not suitable. However, the reference does not address route computation or path extraction mechanisms.
In A. Iwata, R. Izmailov, H. Suzuki and B. Sengupta, xe2x80x9cPNNI routing algorithms for multimedia ATM internet,xe2x80x9d NEC Research and Development, vol. 38, 1997, a set of route precomputation policies are proposed that optimize various criteria such a connection blocking and set-up latency. The algorithms attempt to locate routes that satisfy several QoS requirements through an iterative search of precomputed paths (optimized for hop-count) followed, if necessary, by several on-demand calculations that optimize different additive QoS parameters.
Other research has focused on detailed performance evaluation to compare precomputed and on-demand routing under different network, traffic and staleness configurations. For example, G. Apostolopoulos and S. K. Tripathi, xe2x80x9cOn the effectiveness of path pre-computation in reducing the processing cost of on-demand QoS path computation,xe2x80x9d Proceedings of IEEE Symposium on Computers and Communications, (Athens, Greece), June 1998, evaluates the performance and processing overhead of a specific path precomputation algorithm. The study adopts a Bellman-Ford-based algorithm and evaluates a purely periodic precomputation scheme under a variety of traffic and network configurations. The study presents a detailed cost model of route computation to compare the overhead of on-demand and precomputed strategies. As part of a broader study of QoS routing, Q. Ma and P. Steenkiste, xe2x80x9cOn path selection for traffic with bandwidth guarantees,xe2x80x9d in Proceedings of IEEE International Conference on Network Protocols, (Atlanta, Ga.), October 1997, describes a class-based scheme that precomputes a set of routes for different bandwidth classes. The evaluation compares the performance of several algorithms for class-based path computation to on-demand computation. However, neither of these references proposes any particular strategy for path storage or extraction of routes but instead focus on performance trends.
Other studies consider different mechanisms to precompute paths for multiple destination nodes and connection QoS requirements. For example, R. Guerin, A. Orda, and D. Williams, xe2x80x9cQoS routing mechanisms and OSPF extensions,xe2x80x9d in Proceedings of IEEE GLOBECOM, (Phoenix, Ariz.), Nov. 1997 proposes a Dijkstra-based algorithm that computes minimum-hop paths for different bandwidth classes. Another algorithm introduced in J.-Y. Le Boudec and T. Przygienda, xe2x80x9cA route pre-computation algorithm for integrated service networks,xe2x80x9d Journal of Network and Systems Management, vol. 3, no. 4, pp. 427-449, 1995 precomputes a set of extremal routes to all destinations such that no other route has both higher bottleneck bandwidth and smaller hop-count. The Bellman-Ford-based algorithm in R. Guerin, A. Orda, and D. Williams, xe2x80x9cQoS routing mechanisms and OSPF extensions,xe2x80x9d in Proceedings of IEEE GLOBECOM, (Phoenix, Ariz.), November 1997 uses a similar optimization criterion to construct a next-hop routing table with multiple routing entries for each destination.
However, none of these studies consider computation overheads or efficient mechanisms to store precomputed paths and apply the most recent link-state information.
A significant issue with source directed routing concerns the most efficient data structure to store the set of shortest path costs. Some network routes will be very short (e.g. two adjacent nodes). However, other routes spanning the entire network will be long. Thus, an efficient data structure for storing these routes becomes important. In the typical scenario, a data structure modeling the Dijkstra directed graph is used to compute the routes. The routes are then extracted and loaded into a table type of data structure. Upon computation of these routes, the Dijkstra data structure is deleted. In particular, source-directed routing requires the source to maintain a variable-length list of all links on the path to the destination. This list (or stack) becomes part of the signaling message that establishes a connection (e.g., a xe2x80x9cdesignated transit listxe2x80x9d in PNNI or an xe2x80x9cexplicit route advertisementxe2x80x9d in the QoS extensions to OSPF).
Path precomputation schemes benefit from having multiple candidate routes to each destination to balance network load and have additional routing choices in the case of signaling failure. However, computing and extracting multiple routes further adds to the computational and storage complexity in known methods for network route computation. In addition, since link-state information changes over time, these cached routes must be invalidated and/or recomputed periodically. For example, a switch might precompute the k greater than 1 shortest paths (in terms of hop-count or other cost) to each destination. Alternatively, a routing algorithm might compute all paths within some additive or multiplicative factor xcex5 of the best path. However, these approaches introduce considerable computational complexity. For example, computing the k shortest paths for a single destination in a directed graph has complexity as high as O(kN3) (where k=a constant and N=the number of nodes in the network). In addition, the k shortest paths (or paths within ∞ of optimal) to one node may not be part of the best routes to other destinations and it is not usually possible to store these multiple routes in a compact, shortest-path graph representation.
Thus, there is a need for efficient methods for calculating and storing precomputed network paths that address the following questions:
How should precomputed routes be stored?
How should multiple routes be computed?
How much work should be performed at connection arrival?
How should routing and signaling overheads be limited?
The present invention provides a method and system for computing and storing minimum-cost routes to all destination nodes in a network. According to one embodiment, the present invention is applied in the context of computing QoS routes using a source-directed connection-oriented routing environment. The route computation scheme employs an extension to Dijkstra""s algorithm coupled with discretized link costs to generate a shortest-path graph with one or more routes to each destination. The present invention provides a compact data structure for storing at least one minimum-cost route to each destination node in a network. In particular, the routes are stored using a directed acyclic graph representing at least one minimum-cost pre-computed route for each destination node in the network. Each destination node in the network is associated with one or more parent pointers pointing to an upstream node in network that lies along a minimum-cost route. Routes are retained in the data structure and not extracted until connection arrival.
Upon connection arrival, a route is extracted from the data structure by performing a depth-first search of the acyclic graph, which returns the first route in the common case. As part of the route extraction process, the feasibility of each link in the route is determined based upon a recent link-state. Links that are infeasible are excluded from the extracted route. In addition, according to one embodiment, promising routes are re-ranked in the data structure to provide computational benefits for future route extractions.